package lesson4;

//折半查找/二分查找
public class Demo5 {
    public static void main(String[] args) {
        int[] arr = {7798,22,45,12,67,89,123,12,56,88,99};
        sort(arr);
        printArr(arr);
        //折半查找
        int index = binarySearch(arr,67);
        System.out.println(index);
    }

    static void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i]+"  ");
        }
        System.out.println();
    }


    /**
     * 折半/二分查找
     * 前提是数组有序
     * @param arr  要查找的数组
     * @param value 要查找的元素
     * @return 如果查到，返回元素下表，如果没有查到，返回-1
     */
    static int binarySearch(int[] arr, int value) {
        int minIndex = 0;
        int maxIndex = arr.length - 1;
        int middleValue = arr[(minIndex+maxIndex)/2];

        while(minIndex<maxIndex){
            if(value>middleValue){
                minIndex = (minIndex+maxIndex)/2+1;
            }
            if(value < middleValue){
                maxIndex = (minIndex+maxIndex)/2-1;
            }
            if(value == middleValue){
                return (minIndex+maxIndex)/2;
            }
            middleValue = arr[(minIndex+maxIndex)/2];
        }
        return -1;
    }

    //排序
    static void sort(int[] arr){
        for(int i = 0; i < arr.length-1; i++){  //冒泡排序循环次数
            for(int k = 0; k < arr.length-1-i; k++){//每次循环下标的范围
                if(arr[k]>arr[k+1]){
                    //交换
                    int temp = arr[k];
                    arr[k] = arr[k+1];
                    arr[k+1] = temp;
                }
            }
        }
    }
}
